package org.example.algorithm.dp;

import java.util.Arrays;

/**
 * 322. 零钱兑换
 *
 * int[] coins = {1, 3, 2, 5, 7};
 * int amount = 14;
 */
public class CoinChangeSolution {

    public static void main(String[] args) {
        int[] nums = {2};
        int target = 3;
        CoinChangeSolution solution = new CoinChangeSolution();
        int res = solution.coinChange4(nums, target);
        System.out.println(res);
    }

    public static int coinChange3(int[] coins, int amount, int[] minLenArr) {
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        if (minLenArr[amount] != 0) {
            return minLenArr[amount];
        }
        for (int coin: coins) {
            int tempMinLen = coinChange3(coins,amount-coin, minLenArr);
            if (tempMinLen >= 0) {
                if (minLenArr[amount] == 0) {
                    minLenArr[amount] =  tempMinLen + 1;
                } else {
                    minLenArr[amount] = Math.min(tempMinLen + 1, minLenArr[amount]);
                }
            }
        }
        if (minLenArr[amount] == 0) {
            minLenArr[amount] = -1;
        }
        return minLenArr[amount];
    }

    public static int coinChange(int[] coins, int amount) {
        int[] minLenArr = new int[amount+1];
        Arrays.fill(minLenArr, amount+1);
        minLenArr[0] = 0;
        for (int i=1;i<minLenArr.length;i++) {
            for (int coin:coins) {
                if (i>=coin) {
                    minLenArr[i] = Math.min(minLenArr[i], minLenArr[i-coin] + 1);
                }
            }
        }
        return minLenArr[amount] > amount ? -1 : minLenArr[amount];
    }

    public static int coinChange2(int[] coins, int amount) {
        int[] minLenArr = new int[amount + 1];
        minLenArr[0] = 0;
        for (int i = 1; i < minLenArr.length; i++) {
            minLenArr[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i < minLenArr.length; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i >= coins[j] && minLenArr[i-coins[j]] != Integer.MAX_VALUE) {
                    minLenArr[i] = Math.min(minLenArr[i], minLenArr[i-coins[j]] + 1);
                }
            }
        }
        return minLenArr[amount] == Integer.MAX_VALUE ? -1 : minLenArr[amount];
    }

    public int coinChange4(int[] coins, int amount) {
        int len = coins.length;
        int[][] mem = new int[len][amount+1];
        for (int[] row: mem) {
            Arrays.fill(row, -1);
        }
        dfs(coins, amount, len-1, mem);
        return mem[len-1][amount] >= Integer.MAX_VALUE / 2 ? -1 : mem[len-1][amount];
    }

    private int dfs(int[] coins, int amount, int index, int[][] mem) {
        if (index < 0) {
            if (amount == 0) {
                return 0;
            } else {
                return Integer.MAX_VALUE / 2;
            }
        }
        if (mem[index][amount] != -1) {
            return mem[index][amount];
        }
        if (coins[index] > amount) {
            return mem[index][amount] = dfs(coins, amount, index-1, mem);
        }
        return mem[index][amount] = Math.min(dfs(coins, amount, index-1, mem), dfs(coins, amount-coins[index], index, mem) + 1);
    }
}
